package Utils;

import BasicDataStructures.TreeNode;

import java.util.LinkedList;
import java.util.Stack;

public class TreeUtils {
    //以层序给出数据
    //如果有空的怎么办？
    public static TreeNode generateTree(String data) {
        char[] str = data.toCharArray();
        if (str.length < 1) return null;
        TreeNode root = new TreeNode(str[0] - '0');
        LinkedList<TreeNode> list = new LinkedList<>();
        list.offer(root);
        for (int i = 0; (i << 1) + 1 < str.length; i++) {
            if (str[i] != '#') {
                TreeNode cur = list.poll();
                assert cur != null;
                int l = (i << 1) + 1;
                int r = (i << 1) + 2;
                if (l < str.length && str[l] != '#') {
                    cur.left = new TreeNode(str[l] - '0');
                    list.offer(cur.left);
                }
                if (r < str.length && str[r] != '#') {
                    cur.right = new TreeNode(str[r] - '0');
                    list.offer(cur.right);
                }
            }
        }
//        LinkedList<TreeNode> list = new LinkedList<>();
//        list.offer(root);
//        int dataIndex = 0;
//        while (!list.isEmpty()) {
//            int size = list.size();
//            for (int i = 0; i < size; i++) {
//                TreeNode cur = list.poll();
//                assert cur != null;
//                int l = (dataIndex << 1) + 1;
//                int r = (dataIndex << 1) + 2;
//                if (l < data.length && !"#".equals(data[l])) {
//                    cur.left = new TreeNode(Integer.parseInt(data[l]));
//                    list.offer(cur.left);
//                }
//                if (r < data.length && !"#".equals(data[r])) {
//                    cur.right = new TreeNode(Integer.parseInt(data[r]));
//                    list.offer(cur.right);
//                }
//                dataIndex++;
//            }
//        }
        return root;
    }

    public static void printTree(TreeNode root, String method, boolean recursive) {
        String m = method.toLowerCase();
        switch (m) {
            case "pre":
                if (recursive) {
                    System.out.println("Performing recursive " + m + "order traverse:");
                    printTreePreOrder(root);
                } else {
                    System.out.println("Performing non-recursive " + m + "order traverse:");
                    preOrderIter(root);
                }
                break;
            case "in":
                if (recursive) {
                    System.out.println("Performing recursive " + m + "order traverse:");
                    printTreeInOrder(root);
                } else {
                    System.out.println("Performing non-recursive " + m + "order traverse:");
                    inOrderIter(root);
                }
                break;
            case "post":
                if (recursive) {
                    System.out.println("Performing recursive " + m + "order traverse:");
                    printTreePostOrder(root);
                } else {
                    System.out.println("Performing non-recursive " + m + "order traverse:");
//                    postOrderIter(root);
                    postIterOneStack(root);
                }
                break;
            default:
                System.out.println("No such method...");
        }
        System.out.println();
    }

    private static void printTreePreOrder(TreeNode cur) {
        if (cur != null) {
            System.out.print(cur.val + " ");
            printTreePreOrder(cur.left);
            printTreePreOrder(cur.right);
        }
    }

    private static void printTreeInOrder(TreeNode cur) {
        if (cur != null) {
            printTreeInOrder(cur.left);
            System.out.print(cur.val + " ");
            printTreeInOrder(cur.right);
        }
    }

    private static void printTreePostOrder(TreeNode cur) {
        if (cur != null) {
            printTreePostOrder(cur.left);
            printTreePostOrder(cur.right);
            System.out.print(cur.val + " ");
        }
    }

    public static void preOrderIter(TreeNode node) {
        if (node != null) {
            Stack<TreeNode> stack = new Stack<>();
//            TreeNode[] s = new TreeNode[10];
            stack.push(node);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                System.out.print(cur.val + " ");
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
            System.out.println();
        }
    }

    //这个压栈的过程是在模仿递归系统自动压栈
    //对于一个被压入栈中的节点来说，只有他的左树处理完之后，他才会弹出
    //当他弹出的时候，再把自己的右树压栈，重复步骤
    //以他的父节点视角，只有他自己弄完了，才轮到他的父节点。
    public static void inOrderIter(TreeNode node) {
        if (node != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (node != null || !stack.isEmpty()) {
                if (node != null) {
                    stack.push(node);
                    node = node.left;
                } else {
                    node = stack.pop();
                    System.out.print(node.val + " ");
                    node = node.right;
                }
            }
            System.out.println();
        }
    }

    //O(n)的额外空间复杂度，两个栈，好想不推荐
    public static void postOrderIter(TreeNode node) {
        if (node != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> rev = new Stack<>();
            stack.push(node);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                rev.push(cur);
                if (cur.left != null) {
                    stack.push(cur.left);
                }
                if (cur.right != null) {
                    stack.push(cur.right);
                }
            }
            while (!rev.isEmpty()) {
                System.out.print(rev.pop().val + " ");
            }
            System.out.println();
        }
    }

    //后序：左右中
    //对于任意节点，处理完左右后再弄自己
    //所以需要一种机制知道自己的左处理完，右处理完，以及全部处理完成
    //用一个变量记录上一个弹栈的节点是什么
    public static void postIterOneStack(TreeNode node) {
        if(node != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(node);
            //node的含义：
            //1. 如果没有任何节点被打印，node始终表示根节点
            //2. 如果打印了，node就是上次打印的节点
            while(!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if(cur.left != null && node != cur.left && node != cur.right) {
                    //如果有左树且左树没处理过
                    //为什么需要node != cur.right?
                    stack.push(cur.left);
                }else if(cur.right != null && node != cur.right) {
                    //有右树且右树没处理过
                    stack.push(cur.right);
                }else {
                    //如果左右树都处理过了，打印当前节点，并且node指向cur,记录这个节点
                    System.out.print(cur.val + " ");
                    node = stack.pop();
                }
            }
            System.out.println();
        }
    }
}
